﻿// 176. 装满的油箱.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
https://www.acwing.com/problem/content/178/
有 N 个城市（编号 0、1…N−1）和 M 条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过 100 个问题，在每个问题中，请计算出一架油箱容量为 C 的车子，从起点城市 S 开到终点城市 E 至少要花多少油钱？

注意： 假定车子初始时油箱是空的。

输入格式
第一行包含两个整数 N 和 M。

第二行包含 N 个整数，代表 N 个城市的单位油价，第 i 个数即为第 i 个城市的油价 pi。

接下来 M 行，每行包括三个整数 u,v,d，表示城市 u 与城市 v 之间存在道路，且车子从 u 到 v 需要消耗的油量为 d。

接下来一行包含一个整数 q，代表问题数量。

接下来 q 行，每行包含三个整数 C、S、E，分别表示车子油箱容量 C、起点城市 S、终点城市 E。

输出格式
对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出 impossible。

每个结果占一行。

数据范围
1≤N≤1000,
1≤M≤10000,
1≤pi≤100,
1≤d≤100,
1≤C≤100,
1≤q≤100。

输入样例：
5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4
输出样例：
170
impossible
*/
int main()
{
    std::cout << "Hello World!\n";
}

 